//48_快排.js

function quicksort(req) {
    return sort(req,0,req.length-1)
}

function sort(req,left,right) {//递归函数

    if(left >= right) return req//如果左右指针中间已没有其他值，则直接返回

    let value = req[right]//使用最右边的值作为基准值

    let i = left
    for(let j = left;j < right;j++){
        if(req[j] < value){//如果当前值比基准值小，则往前提
            exchange(req,i,j)
            i++//i始终指向第一个大于等于基准值的元素
        }
    }

    exchange(req,i,right)//把基准值移到最中间，本次的基准值不参与下一轮排序

    sort(req,left,i-1)//递归基准值左边的部分
    sort(req,i+1,right)//递归基准值右边的部分

    return req
}

function exchange(req,a,b) {//交换数组中两个数的位置
    let data = req[a]
    req[a] = req[b]
    req[b] = data
}


let arr = [1,5,6,7,2,4,1,5,7,9,6]
console.log(quicksort(arr))